{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# NumPy 实现k均值聚类算法（k-means）\n",
    "\n",
    "机器学习中有两大类问题，一个是分类，一个是聚类。\n",
    "\n",
    "**分类**是根据一些给定的一直类别标号的样本，训练某种学习机器，使它能够对未知类别的样本进行分类。这属于 **supervised learning（监督学习）**。\n",
    "\n",
    "**聚类**指事项并不知道任何样本的类别标号，希望通过某种算法把一组未知类别的样本划分成若干类别，在机器学习中这被称作 **unsupervised learning（无监督学习）**。"
   ]
  },
  {
   "attachments": {
    "image4.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQ4AAABICAIAAACIpYw3AAAABmJLR0QA/wD/AP+gvaeTAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAcrUlEQVR4nO2dZ0AURxvHn+v03o5eBEGadASlCSrYiPG1RKOJJfYEY4lGjRpL1BSNUWOJGhULdkUFuzSRKihNeu8c5Q6ubXk/YIET5U44ziT7+3azM7PPzu1/6jOzJBzHgYCAoDfIsjaAgOCfASEVAgKxIKRCQCAWVFkb8F8BQ1Een8fj8uhyCkqK8rI2h0BiiFZlgOBymhOiI0b6DP/75hNZ20LwIRBSGSAUVbU05MntGN3d2VbWthB8CIRUBo64+CdGQ1ydLHRkbQjBh0CMVQYKtDU+JXOo35yKooKWNraAzzMwtTRiasvaLAJxIVqVAaIqOz2/ih8ydqSgnXX4j91VLK6KkoKsjSKQAKJVGSDiYmPVjS2ZcnhNSc2spaud7G3k6UTh/5MgWpUBAUceP0mhKzKO793JVbXxcrEndPKPg5DKQNBelZdTXKmiqpaVnfEsO0/W5hB8CIRUBoKU1JQ2XHH1tyvG+XslPk4EAF5HB0r4qf6jIKQyAGAJcY9U9G3srIzc3RyzE6NPXrpRWFoja6sIJIPoMUsdnM+hKOhNnuyrSCPbeY6aFBCP4nKmpoYUkqwtI5AEErFfpb/AcZxE6uH1xzGUzemQU5CnU6kAwO3gUGjydBplwA0k6BNEq9IfoJy/j54qq22k016WJ4ahCIK8rIVIJBqVimEYiqIkEolKpWIYiqJY1wzIZDKVSiORAMUwHVObedM/IZOJRufjgpBKf0DGM+Kifg+PfBNApSnKy6EoKk6jTSZTOto5r+PpO4+eNTVUjpDKRwYhlf6ApLxu686i0pIb8VmdAfKKOt9v2ehgzhQiaK+pKRRKW0tT9tOUM2fOlNY2Qwefi2NyAzjj0tbU0IFgerq6eVlpCEWFqa0mr6qpQPvvTfngaGlxkYq2oYZKT44UOEE/UZD+0GmQ/qtypU1b+D1fwhyS71+xNtJR17ErbxdKxcSeKMx7fu7CpSYWC8f4n4V4TV+0rqY0/8LFy2U1TQNmw8dAbsqj/40bZW9r7Tncd/vecB4mGoGyadOmgVPtvxoNpulgU63bkbc4QhQAy0pNrBcqBwcME78nZWBmrSxsSHyaM+nzr3SVadI09iVlBc9OnDrvEzLZVF8LABTkFYa6DXO0tWkue379/mOzwfaqCvQBMEPm1FeXHPzzoO3wsTM/+199btL+w8fUzBw97Qd1iyQLAf+b+fv3zXKvZrco8qo7j1ySKHlTcZKnk0NMbr2UzOsKym3bvmbxD3vC376ECfkrFny+88/T2FuV678RtKog/dq9lM4fgrZqb3uz4aHzRCJJpT8q6Ghrbu2QRs7igCPC1uYWWU2Bz14Utn7Z551DQJTbunPTmqsxT8VPrsS0dnew4PNES4/fzs5+/qyOxQYAHEOL8rKLKmr7aGp+Rtzl6MdBY0YDAABelJ8TfePatdvxAECi0gOHO185d/JFZWMf7/JRwWtjpaZntvP4AIALuc8zn1XVNwGQmRaOE0a6dsahKTMdhpjp6miLvELiSqWyJP/E4QP7Dxw8fvz48ePH9u/b99fR4zmFZW+/kU8fPwg/e6muRWZSwRDBi/SEA0fDK1ntMrg9TWXJyvVTg4d1/mJVFaxeuiT1RbmYqak0xS8Xhlnpq4mE1xXnrPpmaVRiNgCgAu6ezav2nrzeR0tvXrnMp+s6Wmp1/izIzZg7a/rRczc6fzo4OHAq8x6k5vTxLh8V1c8TZs5eWlDTCABYc+XyJV9HRMcDAIn0Rgg4r7mKhUwKHSfScRZXKkKBoLmp6dCvW+bMmTNnztzfj5xrYrF4fIGIVK6cPHT0zHUd8yFWJlp9eaS+QJFTtLKzRevz1n63NjWndOANUGNabPtt/3AH086fBVmJy5avLa9vEyctmUIZ6uljoqMqEk4ikxkMBpXS+X+RaHQGjdq32UscT3v+TElXV/nlK0AaM/Ez/2FD6S9vATpMXQVFenJSOvbuPP5xkCgUOTkGuXOlmERmMBhUquha8M0LJ83dQiYEuIuEiysVs8F2YWs3fP3l/wBAXcfsSPiF71atcLa17Jr+7MEde09HTf8qbJy/h2wnGtV0Tb9e9b0zE5Z/vSg1t3LgDTCxdtq7Z7ex7svG4UnUhXXbd7dwkb7k2dUVgETq0TFAEnB+fV2TghzjTQiG0Ojyr5c+qcrqNDqjqroa+3e5c4gWY/erhRkJaaXtixbNVWKI1kSSvdIvCgoBwN4rcIQ9U+RSbOSptT8dmbHga+9XtamMoSp8vW67qVzb0mVhVc28gb+/k3/onh3r1OidlZbwzJ+7fjt8pvdFlgGDRCKTQWTZB8dFmhASmfIfWgplVeTFJWWNnTzLyrCzT9StkpBAKkhzyZOMPADwCQwSSVZXmr0qLGyQe9DUiQF9tbf/oDCUNv6wrjDt7rpte2TSi/hk9rIf1y7prJ0wQcdPG1aejYyThSE9QaLrM/XYbZw3IWQqlUKhvOrXoZxWoYBnZmryH9FKW33pzXuxli4+zjaGGIo01FZU1DR1jSCBVNITEwpKK8nyWiN9vbqG4zga8ddvyaXc0NAJyu91AmSxWK0criT294CQ185pbxcKRTszQgGP09Ym7O5bNch9TIi7xdUTB6KT8/t43w+BxJi/fP2i6aM6fyHshlVhyx6mv5CBJT1A8h3hxW+sqxO+/N1QVZqTl1eQ/6Ke1QoAFaXl7Vx8hLe7VJWCYQibzeFyeSIOQBgqbG9vb+/o69vSK51dsMr8p4vmf/XrgRMXTx9atnTJgq/mLwtb3Szo1geTYGiYmJhc38Y3cfJ3ttLrGl5fmrXnYLihtZObu8c7kuIPoy4npGSz2a3VDc2Wg23GhExwdxws6VMBQF153uYtO0iqxosXL7Y1f2NGSXbKvn2HmylaWzet0dfqOiYmjx8fcurOtmN/HRvpvoPxdo5SRk5V+/vtvxeUTY5+nA0AtcWZy5aGXYw4aW0klbNauGxWzIM7WYXVioqKZBIIEWSIo0fAcNeC7LTYhCQBChxOu4dvkI/7UAAYNe7T8CsxKZnl41yNAfDmxobhQaGgqNvYwtHRUM14msa09vBxspKGnZ3gQs75U8du3H8ydvpXU8b6dalmkaN//JzwNDdw0tyZE/2kZ8Br6mqq5NT0nTXJrCZWZ4ite6C9Sfd5SHFXabisz8f7AMCslbtElqUu/bkJAHyCp7cIekjHa67d8t3iUSHjt/+29+rlCz+tXaJAATMb59M34yVcJ8JxHL18eAsA2HiFFDWyu4RjB7evAgAb/2n1LVyRNPnxl0kAzMGuSfl1kt+xfyhMf2hvYfC6zMfOWFbTLJnXS3lW8ifBQaeiknAcF3I5387+ZOXOo29Ha29tuBZxfOKrJQJVbbNbcck4jr94nuLvYAgA46fPuxv/cq0NRYR/7dkU9v2uHu7HZ61atuBoxE1E0keVhJqCZ8MsVAHg8IU7XcPrCpOs9VUB4OSd9P69Y3HizaFugZklVTiOI/WFY0eO3ns6Usy04rYq5fmZ2bl5ABAY6Nd11gDHkRs3bgIA09Rc9W1XDKT9p42r9pyNjYi8NdpjCABM/GRSTkbGqaiEVStWeHo8MteUE9MAAED4vMjLVwAo48ZNMNdUeh3ewaqKi4sFgFkzpmiqimaoZmJprEQqK8pNTEx0t5zYY861lSUFJb1PlCEIyjQ0sbY0E9/mTiyc/Pbu2DhjwbfVLA4A3Dx7cKu52c6NyxX7e9OKgorWhClfjB4TvGDm5BOR8Rq6TAMjcwAwMzZQVtdfumHFL5vDGK/+PjKFOvWLRZxDf998mBzi/6ajheP4/dtRRrbe/xs3Uqq7avKy09KLWy3dQnw8XLqGP7p9p7iulWnnH+JlJ837S4a4Usl4lvWipF5e387DrtuLgrKrUzOLAUBHT/ftVI9uXfj9z1Ohy3d36gQAAMhBowOvPExDO9jtQskG27UFqdcePFXVs/AP8O8aXpibFReXRtEcNMLF7u2xF11B28xEuyy7Pj8vHwfoqeeNx948992OQzgO75+CxTBswrSFf+xcK5HZnfh9+uWWsuLvNu9pZPMAE+IYypDahDpDRXfrrp8zsz7JyErcsu2XU/s27dn2A2bosnH1Ekb351NS1Zm3YE5M7JPcgpIhnVUAKszOyOArGnw5011JQYo9VoTHvnvzCh+HwFEBgww13lzA2TEJiQIUxoZO0lAcCEc4MRFPKpjwWcbTdhT8fQJ01VW6XmkoK6jndAAwNFQ1RRLhKCfy2vUWIYwKHN41fPqiFfqDPRia+kN0JDsQ/t7NKywB7mHvNMy9Swcax54mx5dzEL/gQCszk7dTUclULU1tgPqKqspWBNR6eGKS84jRWxQNe5UKgiAW1g4S2dzlJtQ5KzbH3Ht4Mjop5LNFP6z+mirN8bKhtedP29ZNmr3sSsTpuexiLk7btPkHLaUe3jxFVa3RY0Yh+Ou2hmppa2dNl6P2NPMl4HW0tnGwd+z3fA2GYnQ5OXV1tfdEaqorv37jDkVO18vTo+ve6bKszKTkdCDTJ4b4f1Rzb2JJpa229GlqKgD4+Xgrd3c1bW5gIUIEgE6jifZ82LWVhQUFABQNtW6SoNKVR44JlthStONq5G0gUYb5jer6D7Q31969FQlACfQdrq3agxsshUJWVlAEAHYrp70dV1PtofwHDXEeNMRZYpMkJCfpYUxypqWL/0/bt+iqSN1jN+iT2WueJP24N/zMuYrjVx+5DDZ6V0wKjf6mo0UiMeTeWYWlPrjyzbodLe18Cvl9baKAL3DxDj4Rvv/d52fiOSkxWTU8O+8AD5dutU9K0pOswlpjt7FOlu80WCaIJZWiooInGTkkRS1PJxuREkIRrHOh5u1apo3d1spuBUBbWvthyq/sWdzjzGJ5Vd2x48Z0Da8oybsT/0xZb4i7q8u70nauJWEYhqHv6IJJn+qi5/PnzmfRjc7v2+dgItoCSwOKnPLs+YsPHgmv4cL9e4+mhoyQ7/NuLXVtA+8RPlx+724Hppa27xnnYKjw5pXLAODu4TWI+aafgvBaEh/H8QEmThir1b3/InPEkQqWk5lS3Yo4jAyyMjcVuSanSCdRyACoUCgQzZpK62xq0jNzpgS6ivxLAgGvoqLGwkLcIfKtyBuNHL6D7zBve8M3oTia8ii6gQejfUe4iewu6EJnb4HGoNEYPeukICs1IfV5b90K4PME1vbOvt6uYtr8mvamynXfLnqc3bD/7PUxnkN6T9AfYMKO6OhoKyd3ubKi8IO/uHq6fjNjbB/ztHHz2+Pm13fb2mqLrt6Opytrj/Dt1suqLHrx4G4sKOmO8h3G+MgO6hCVSkX+s4ir0R7+Y0e4vfwMCI/d9PDubQAIHRdkqK0sEl/PyEhBjgFsNpvTLHJJU1NLV1cHoOBqxJmwOVP01bv10NJjo7JbVMSVipB15+FjHGD0xEnyXYpWyG29cPYCkBR8/fzVFHqWPYZhHG4HAOjoaGko9CgF/PGdK4vX/9arVBAhOm3eSomlgnL279p04nrC8q0HFk4LkixtH4iKOH7+7rMDx8Lvndn7zY/7fly7xt3FcZi1Ye8ppU/yw1tFTXxrV3t//26FmZEU97yyxXn0DMchvSy7sVk1TWxhdX7GteSSpbNCldR11JWk+y20bq9XR2vdykXzLseme4dknTh+xESDAQDF2WkRNxINbDzHjw56eySqxLS00lcrb2hreLV28xqamr6zo+PpGwkFqfe27D60Z8MyxqsOQHl+2oGDpxbvOPjyvhw2ly9UVVfvcSgJAHkpCRk5BUCVGzHC+3Ugn9fx5O6V2+mlWsZ2I3x8EHZjZbPAwIBJ637AlhAR1tRUAoChoTG95+xJ42cuGTpyyvvK6RVqGhIvHV46fuCH3X9Pmrdy83cLB8yLtDg9ZvdfF79av2vIYEvzr1ffexQfGZuxZvX6q+ePq8vJfLSMX792EwDMhww1UX4zZqsuLbh48SwKpADf4Uaa8gVZOQZWlgr0HqYiaktyEp8WuAwbbmlt40fTQ3nsyOsJPv4hpkzRzQv9SHepNJVFPUpBMCBTKGQSGQAQTuPP2zZzgLEhbLmrTQ8VEomm4jfC/V5meW15qQCg21iVRBkfOvl0xKX0wrpDO79nN1bP/SxUQ1mhMOPJzt/2OoyZ5TlIBwBKs58sXrz0cWb5/FXrNq9cqtBDu4tHR98prWeT6YolBS8EQw15nObiwoKMrOeRp48LcGAa6OtoUi+cizBw9DIx1hdJLGivLSxpoajqOzo5vasUNHT0NXREE/YLT25HLFiyZrB36LaN65SlOufVBW5T1Q9bfxo5beHUQDcAkNM0+nnntrxPZ8RGnv7xF8/f1i+UrVYaC5LuJz0HgNbG2qbmNjVFellpSXFpSezDe3cepAPImRjpV5dn3YhJmWdmBm9JRcBlnbl0w9B2mBFTExEq+WgYKMgzlBJjLl88v2DBHEXpnZvedT2S01IZYKsPAL+djMJxvLI4d+XcT1U09dfvPPieteWUOxFUAFuvUfkNPcS6emqfkbbo7gvvUdNKGto6I+zb8s3LULrK0WuP386Byyr5NPBlM62uY/jlVwtmz54xbdrcqEdJK2eOAQBFDb0x4z/Zuf/vutYeDMi4Gw4Adt7BZU08Mddl+4uKvCQ3c21106EP0/L7mJWYq/U4jhXlPvtivC9difkgNRt56VeBNdWVBziadhby5t1/l1TWoajMtgKH71776nWmDg8ct2j+nCmTJ+/846/HMTc6++iu3r5zFixNyy3uMXlidMSC+QuLm/g4wj15ZO+mnX/gOM4qTJ4yddbD1Nz337rfVusVVQ127t3/48+HizLiT0F9QU5mBVfpePjZSWN83iM2e6+AsZ5mt3Pzs7NyLf0cRa5OnLlEVUP3zyMn0p4+ZbEF+qbmQcHjw5YtNdF6OexxcvV0sb3djtPa2S0pyalzJgwTySHx0YM2XPHTKVOeJye2ctGyssqRo0Lmzf1CR1WBXxh4OSYDpanqWzpM+TRUp6cZ2ISYR2QaPXjCZGONAXUB47Eqly9ZlFKFnri418/ZcmBuivDa4+9HlbVh3m72yYnxdtZW2opUwPiJcXGaFg6jdK1QFEmJuanP1Jo6PlBZmiuM7wLnNUfeS544dRqroiSrsJRVX8O3MJ23fFmQ19C2uqJgH5e4vGoGjTZh6ixn657HsXlZzxo7wEiDDgI2p6Eq7YUAANRNzXmsimf5pX4u1lKyXLS1cg0IDR/qkZSc2sLmBX86a4OrY6/rpQxFzW/XboiaOCcmNi70LakAgF/IZC/foOdZWa0diJ6RyZBBpl2veo353ylDG54AO7F/K11VSTSxkH3t6jUDx6A/t6/IyUjvEJIdnF1UFF4aNX7WUqaNG8ipuTk79NypELRevHHfzNZ76RyxhiL9BtK+bcO3F++nb9wbPmvcCElT11SV5ZfU+w53kzQhiUIbPXnWqMlfkEm4UIgovxycUZ29/Jy8AjoPv0SEfASnyOok2PTYm/kNguO//6pN6cgvq2Yamg22eLl+oqJrvv/U2dzi2iF2Dnpaoj2RV+AtLW24nCoVAOjKTvY2MeW5AAAURXmasNMnWkr00LFT0WAGjRkvSSYk7+DPwr68Hn727y9mfOpoIbrrCwDoiqouHt5vhwMAAMXGzpFdV1DdIlwWPFLkWkHmkwtRCd/u+lKOIefs4SVylUxjuHu9r8V7cCU8u4a/9cAGY623RChNTu7ftf3AhSmLNqxZMkPixDhy++rZpErKB0iFQmPo6uqJhpKpTKZURmISg3FOnjpHUmXqaWnoqurrm4rM75OYxpZM4/e3wCRlZQVSMQcFoAAIBAIE6XSPEggRmoaKFP/l/pmSodAY67fv8tCnbtmxp4UvmWeXgM+tLs3/efcBv9A5w+2Mu17C+G3HDu2vZtPNDD9kirOlIvfnfcemLVz95ST/3mP3Hw+unQxbvc117Oe/bl0jJ3kB89oabt64pfSWo9C/gKQHUecv3TYfZKekIIGbLACgQkFrWxuXxwcAa1sHFQavvBkHwFva2gV8nhDBeLXlNE0je0tTqdgNAP34fRVlPcsDhw8ymrJ2/fIHq02C5fn856lHDp90DZq86PPQ7p0oPDUu+o+j1zQN9bV1Jf6AdU1FwaaNP1r7Td2yZtlAnjZbmBaz4ptlFEOXA79uMdT4kA+jXjt37O6TfCOTj2IBpB/hsioP799by0WsrEzlJXGDrKupuHUrOjY27tqVi0nPSjx9AhxsLZ6mpQDgGmYO86ePa25rf5KU7uTh5WQvrYEK9O+niPQshh48uE+BW3nyTERNg1gHlACAgYXdyvXrJoz0Fh1soMLI86facXBxcbUylaT/gAmLctMPHTo2yHPsT5tWq3xAxf6hcOpLvvtuNYtudD3yvMvgHnw33wfKL8rL/mvv9rA1W1Eq3Vi/2yNjCNLW2soTCAEAcJzDbuN0yODAgL7wIjf73NV4iqKGl6uD+H9JeV7ath07MHmN8WOD8xNvHD0fSVHWGz8miN+YX1RZP9w3YHzwKGFrVSmHHhISrNXbrgZUKGhubkE6t8piaGtLK5cv6mXyLvq5wlXWMVu/dUf8wwecDnEtUFdX7zEcJ5Ftnb2nTNf5ZuU3usqS2IljLay20ZNmDXO2kSBV3xFytq3/7vL9ZCevkfG3L8VcF+Bif7sGFfKrKkrSUlJTMnMAwGCQmrZutyGfmp7RF/MX2FobAwCZRp84/QuSjhRrUGmgpqkzeeo0W7/xfu7iemdzWup2bNuh7Tx24qjhANhg5+E+dn4AYGHrqqCi2S7owAFIGMLmYQEBI42Zva8Oa5rYrAhbqK+hAgAkJa15i76ydBbbz0iC+fABB0GEXIFU9+H1Jwd2rOqvyVdLB7eCFlTWD9TfoCifL9nez0eXDrt5+uY1iO5slQkf9UcjKBQq5SPzmXsHeNTpP9b+8DO/n7KjUtV1Vf5132wgk+l0SbYeYMLE2ASGmvFgrZdzACiKUmT3QnzUUvnHwG88fy1aXkNXidI/5WnpYK8sc0ct2YNjgDTUVhQ3so1UaE2N9Vl5ZSO8PRgM2RzOT3wLsj/AsQ4uj0Qi9/XEx1eQKdTX38r7L5OVGDV19pJBzj7jgrw5PDRk3EQrY70+n6v5gRBSIfioyXmaGH3nvrqxXeiEYHVFGXjivIaQCgGBWPzrxo4EBNKBkMpHA9G8f9wQUpEKGCJobm7mC3o/rkHI51aXl/x15HB0zOMBMIzggyGkIhVYFTk/bNiQlFPSa8zWusqI00fDvvk2VYzIBDKEkIpU0NAzDgwcyXznpos3aBlbfjZlmo05U4j8mz6P9S+EmLzvb3Cktroqr6BI13iQqZ5YX/kjk8nycpI5pRMMPIRU+h0SQ07h2okD1RTzw/t/UqXi1aVFxZV1FErXBhxHEJLF4MH6Ohrwyg1PVuYSiAkhlf6GRFHXYNTWNZr6hygzKIAJslMfn74VI9/NHQNr55BmLVrYKRWCfwSEVPqf0szUSjZ85uFEBgAyfeQnM3wnTBNxx8AwoMlodzvBh0FIpf9JT0mlyavZWJkDAOBoUW5mdmEP3623d/awMO7hHAKCjxNCKv0Nwk14nGQ8xMVQTxVDUTIgLzKSz9+KfTsiXd2AkMo/CEIq/Ux9aW5aXrlzoFt9TZ2ejhadwhg3c+G4mQvfk4RKofAF/I/oO90EPUGsq/QzAow8aJC5IZOpoqggzsa0jtb6hOQUVQ3d1uri5/nlKDET9rFCeBb3MygiZDU1MhTVVMQ7mB0R8BqbWHy+kEwhK6lqqCkrymg7BkEvEFIhIBALogNGQCAWhFQICMTi/6zWQA/APq6yAAAAAElFTkSuQmCC"
    }
   },
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## K-means\n",
    "\n",
    "k-means 算法是一种很常见的聚类算法，它的基本思想是：通过迭代寻找 k 个聚类的一种划分方案，使得用这 k 个聚类的均值来代表相应各类样本所得的总体误差最小。\n",
    "\n",
    "k-means 算法的基础是最小误差平方和准则。其代价函数是：\n",
    "\n",
    "![image4.png](attachment:image4.png)"
   ]
  },
  {
   "attachments": {
    "image5.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPsAAAAoCAIAAAC3uhtwAAAABmJLR0QA/wD/AP+gvaeTAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAVYUlEQVR4nO2cd3Rc1Z3Hf++9edN7lUYzo65Rt2SrYBs33DA2BhNIMIE1oQSSDSQ5J3842bMnyUk2Z9nd7OZsdjdZNhBIgCRwCNjgCsZV1eq9jzSqoxlNr6/d/UMuki0Jq9kQz+cvzZ377ru/e7/vvt/vd+8IQwhBnDh3Dfid7kCcOLeVuOLj3F3EFR/n7mJ1FE/H6BviA4ZiOI5dlZvFWTwsw7HMrOlAHKIp+k715zay0ornAh57a2WbI3yjugOjXV2dvVNx0d95QrbGpp7eyeisQoyJ+uytdQNTMe4OdWs5IAjZO9paGyvOXWoeHAsvVHVlFU/7BjsunWuyRXECMAwAkLf/5EcXLvdMYjwmONxZU1dtW7A7cVYbdqrtbGWdzR1mCQIAgPX2NFQf+aTFwyGMDvRdPlc95Ax/uUTPMdHJzpqmtq5+W1ftqXf+8OHZZuf8b6uVVDwX6Wlo6OoI5+9bb5LyAAAAizqbGjra7ZO0Ir3MapQ6q45WDlPxfOgdggsH+89/3C615ucXm0QAAEDQTltvdUOfCxNrMtZv0tgvXGroccS+RFPEBd32puOd6pJtex959vmHtP2VJ46+3xmdr/oKKp6butw0OuQy7chXAAAgFPN7PLyUZ7/35ONb84QAkJKfLLNAzcfdwbhvswQQS8cCnkCMYa/KkY0EgsHATQ7kvLBBR8fxy8L85KRkJQAAG40EXFzW1gcOv7w/QwBA8nUF2xO7mgb6u/xfJMkjlo0FnIEYdc1yYGOBYMATZgCA8nv6Guu9oSkaA1Dlr8+adDg+q+5n5mlsBRU/ZWsNugZ1eakkAEKUZ7jmxLH3X/3F/52vsYUxAABQmHR8NV7RNBq5SyWPODoS8PqDUYZbvKIYt63tg9980DbpvjqZ7tq/njx2tNJ1qw1EfaPNFVKzSqUVAQAbGmqtP/H6r1//8+vHh67MEE+emqfpGHL2LewL32YYj7Ptw59+0DpwzXLwtL5/6sj/VEwAAEkCjQKX2wYcfhZAKJXwfFTUFY7M09jKKZ512CnOqbIkEQAQC/qGa2zqbAPp7h3ssXuvKFytVQhVgo4RD/tFWkJuHyFn7VuHH3rhh281DMcWfTFiY2Gvwxumrw0eE/b4fN7QrWZYojHfRIckSaGQyQEARhttTAzpk3nuhnq7b7pNnJQYk5XD3rDDt+j+rSIsFfYMesNh5ppsmIjL5x0LxQCA0KZuf+E3/3nofquSgJCt08ZPUuUXmyTztLVyig9OjbARu0omAQDgCeUJ+eXJhKMfUpQGi5aYrkOIxGFM0ulws3fn2QaC4PMlEhYjuKXYj2E4QRA4hl0rwAmCIHBsoYuuw1ERr6NTJmIFPAwAkDS1KMssj0ZDTsXadD12tUmRTNXviU0GvkiL/E2WA4ZjBIFPm07wpWqTRasQ4szQ2Xeb1Wu2PPT8VsN8yuatWK9oOsrRIT6OAwDwSIE2XW9/56jPvM+YbBQDzQJJAGA4wgiW5RDc4jT9bSFQ5j7w0r+X0+qkBMHSWljGsCGOo2JBArhp4WDKJI2/odsx3iosf9IIYRrEJAAAhhMsizj0RXM8b7Qcu6EIsRNVH3zmVJTtf/Te7FQBQwOfnKudlVvjZWojJjZPha6sDWw40F9/nL+2MJl1DfW1jVAAAGwsLOT86Vol764UPOA8ic6cnZ2mlwlv/2Y3zhcq9VZPDI9NOwc4uFsqpzCnJT8P7z7d4qE5AAAUC01ZlKRGLLrtHVwGHOftrrURiaUPPftIsXKkr7nSNp8fv3JrvMCYJhS4h0ddCNQYAMaxVJRKQMNddlKUiCfwAACCbj8WiOaZNcSXTfFMNBRiBArpyo3XbQcTibSm4nAdEwxHQCUGACbKKDh3wDfWNsJLS8UAALGxqVFvmkFiUH0pLMUAAKhA35l3fvmrVxvJjBzTn4TBHk/a3oOHrPNcsmS7KN9Aa8tghFTKJTwglYlGkzYzW9wbmGgY47KScMAliqz7vrV7OBxTFGSlpOhJAAgPuaJj1JrNFsl8Kxzl7K+rq+omc3dvKDSKV2LQWa+te3AyyJFswBthVTkbihOFAABM0FZz7mJ9ZyBrw5bsFLWr9bw9gnTW++/JVZMAYUdDfXdUIBbQwTBCuNTA2ltGQm7thkM7kyXTTyvr7L144WzNOK9o/YZcvWjK6eboiM/rluRvKtFyg712L4Mo52hQpksvKEuVALBRV8/lTyrbJyKC0j37StN1gsBI7YUz5/sj6cXrS9PVnnEXi2i/cwzPLFubZpx3jBYyNjbZ12kPsLTfK0zLSiCxyNTgkBsnhaLUwjVJIoEyaU3BJ/UeXx6VlMIHUBXs3oondNN6fVZ+roIHAGxouH4i2ZyXPG/gt0zYiL325ABpTM8pN0sAAMLjfX097Zx1e75ButQ3P0Ikqclal+0LU353FEtcm5Oz1iycp/KSREV7J1vOn252BjmZIckdaTx9KrJm95NPPVGamzRVVXu2I/hkvhR4Al3h7gcLr1/FOHoGnQ4md3+uYt4lPjrSeuz1f35P9g1rYY5RzOP8I21dQ5O+CE7MP/+I5eSJ6ekZqeqbjGRDQxWXLnaN44kmDeXuaa51tXRTBw+VGcQYR/nGbDXvvvI2ynvssb8/ZBj85FhNp2xTTlG2nPJ1HXvrWC9rzs8zxMaaL10cURUXp2klaGzcRyG4ongU8Q53nHvjtSblPfue+tqOVCGC2FRf1enac7btpRYljycU8SM9VZ+0Byy7hN/eXyhHTMQ93Hjq3T8e6/iq1pqdphNQgYn+qr/897lYStM3ntufJSH4KGKv/uj8udFDzx3ckqme0w+df1Yo31BDS78jgARooKri1KcKo7U8lb54tKLJLXnml798JFUoNeY/mHbmXO9wZoolTYyTiTkliTkl11rgaFf7RXtC6d5Uq3qVvC5P/4e/eqU+e/83M8rNAABRe8Wp37/5YdqPy7MNS3iBIgAAvjxzxzM/3/HMrV2y+JtwoZGG42+8XcfsfPE7e7O0uKfFduKtgXG7KwLWwvx0j+dcY2VXwqYsjWhmEoELTfU0doUEqm1bsxfwEAUG67aHnjMI1pkkJAAg/1h7fVXrsJfkz/v8IzbGJhURatMcio8On/7TsSHrxqcf3JMBcK8J/9Vvf/Gqsdz6SLGSry567KUfi/o6fvZ+l5PRH3rhcFJ25QhfSVCejorfv3U+8Ts/eXjXWiVElfbLf7A38Ne/9ngGCrOCa93gWUqfOvxzGP3hr9sGfcr0XdvSCaBGRf5T33/1TfqFf/3h0yUaAWxOGn/p3y4dP9q5s7BcIjVvfOIfBILY2CtKkmURgCZn/8s/5U/95GcfDYzhiS88UCwB8Ccyld97u6q0qDBjo34Rax4Xdo22NfWQ9zz0oEnJG+Lee/xfGsstTzxzUO2P0u2URgAAgEuUuTu2VZ4ZaW63qQvSlMIZN2Bpv729rse3btPm9CTFrd94UVBj7RWTJt3mwtTpO1CTtuHRFq5op0FK3iZHd7GKR8zwxWPvffRX+tHXt6RrcQAQGe554kflWpNVCYAZS4rKSaK6bTiYphbxZyreZXMIZfrMbSWqhZoXGHN2PJmz4+pHwlR28FtlBxfZx+tgIoOR7AvYW5uGSJ2Qj4sxOb+6a3CKWqPkEQDAUFTIkJNtzTarFKLN+7MAAIVsjv66SfWjQrkIAECo0zH+7v6OiRBkqcQ3rHwME436kjMz1uSmT+dfEUEmyBj1+gKLclpiQhkewMOj3giABAAYhmE4gBlpBjYSCSSYZcXFBRIAAIQRAiU3Egz6YhwAceumMhGWCsnWlGglPIDQaJ/TmJ5dXGSQKTOefKl0xogILFu+vu7oJ57JkUDqLMVTUZ+zP5S3b1tGhnq++3K03+nwhCI0NzNTeCMitV6jkAlufkuwnHOoqU+XmJeeOf0wI8dIr8fmyn04SyuceU/W1d3iCGLq/KLEJea05mexig8NXq65XDFZ9P2idOl0H4X64nsN1+zHNClrNiXlAo8/22CeuWiTCTD89sZDYvPO57+jrTp/4cjvWxWWFN6YzcXElDP2qjmG02gUWtX11w5GSnXJpZqLQe+Ul80woJDDA1KxJU0z15uJYzmOJ5GIZVe+5DgOcEKokorJafMRQgAYdk3giONmH6PmWJYjhHyx4krQwiGEAANsAUHNDV9tzLwvEeMRGHDMQOuFoE6TmpUpu7kiBsrCBx5m4UZHUShNWrf/AEaS8/szXNTX9el7p1psU4xgzmoIIQA88/6vPripxHizVqnAYGet0LI+I8U0ba1/dMA51Zu0Li1BNEsYjL3q6MVefnFSUWLCLdi+KBarwMmhLtegK/NgboLoqslXZgchuJLoJUj+zRfivKWInWMoimE4biEFIIRwHkmS5E3RAQrYT7/xajWjW3/ghQ1mMTlcOWo7eh4Qx7Esi+HTWwc4NrtxUpFSsLHY+9fmS0051jK6usJrspRufdA6XySEAcDs/SQMu/HHw58v3xta+Nz6c/QDv7qcRCcHuoaMylSrUQMAiEMcx+G8GaOD8cibJwPDcGIBtQMA4EJV4YOH0nfRLFqghxhfIpPOoQBg/CM9nb68NabshOm4GDlHJ9gQuTnHIkIsg3ACxzDgGJrl0ve9aOFIifrzjF4Ci5UhRVECgmcwznoLRSdHvJhAotHJVjjeYUYu//mDs81DHlKwgB8fZU0lu/Y8sDPzRofJWfvOf7RPrdn3tZ2FiSIA8Ev4PAzHuIjPdqEZLypI45M3N8tSQFPJTz9hUYrGm5qQbOvj30y3GDVzDhSGYRhg1x+Zq39eK8GuMasCdmMFmLfC4kHO7tpOpXFHgdWIAUT723vHpriSrYXi5e/64YRQfnO0dItwMUd/vT0pYXuGUTldMNHX5x4Jlz2uwZzNRxslW+5NVUudTWfqupvbgznlxZu36Zfb4TlYrOJ1JqtxTYbDH7nmZdLuxs8ujMuTC0u0y+9ObKzz4menOgTrHt6z3iLl4ZqMjbukuSEKX2ArHbFIojEa5kinRZy2IZZXrjVOOx2T/W2NjcNcGc0xgREnL5fFeAQOGGDEzFFAdDjgmSSythdbE+UsJllos4ggcMAwDCOuPP44geMYBhh+teDKGQAMv7nCFcVfOSRwvQIxXWGh7NQNYAAQnqj5+O0321R/98JXTB0V5yagSJliIAGmBkbHOx2KTfw7vsnNsZ7Rrjovu5m84gOG2itONbXZEh5LJGODbSOCTQxERs/UOAUJpmTqSGe9W19aUi5d3k1j7u6KUyc6Imv3HlifqiIBFq94Vca2rbsDx8+/+9aHay0SOhCI8cRyRbI1I0UjWIExjTm6zx753XsytmRziUXKwyW69BzdklvTlR38bs8HbWf/+Ia/2CAEOiC5976vxRpPvP2XiYLSHfaGsy3Hq/qq/AT55h9hS0FuUZFJCkAqtMmZ+G8Pv/i/iCchgWM5Tpxo3fbYkwe2l5lm+KbMeEd1xfETdc2dQrf2eIV0XVpCqPH9459WdnQPHv8gQSZ7IDE63P7pserGekquPnZWWZaTTLUe+fjUpY5u5ckjRp1+v5l19nz2UUVd7SSSf3xataHQirpOfnTyYkc3//RHxiTTIyVZRtnnzxAGACzlG+9vqKRSzTEpmbh3T24w1PXx+36NiOEnFW7MTLzz+0mx8Gh/tRMfrr9w/qTELQcAlrLkrUOOpks1hEJZtkevEPNiqYVFek3g05NSmtHI5nKNFnlTX8+lI7/70H+ocGvJEhWPi4yF5QfEwhYHqVPyWamMFqhSszIN4kWkFRZAaCrY+8zhDDI3Rba4ZPSciNPue+6g7PLgFJLplSQmsOZv2b6rrLrCTmrz8s1CFy+6+7uvlDBiVYJJp1ZMB090xDFQ1wS6zEKdRiIAAC4SDAcna4596HOhbz5Rrr86YphQpjYXffUH/xjCBfpktVwsFBCJedse+X7WJkFSskUtFohJZWL+ge/+cDsidGlahVTAZwyZG/e9bColE0wmjVggQnJ9zt4Xf7CRRposnUoqIJEupWTXt3+RT2gSjDqZ8Na2ZBAAiLRr9j7/T3khmYxlVNnZ29ePukP+EIhUykRLZqJ4+WO5XOiAw97XnbN19857ylMTpASAQFNQtHZzcLB1QqJXmwu0Ij4GgvQ0OTg6KoJ83JKXunzFCzV5u58+nEHlpGuu6mkJzz5PasjeuDN72b2ZC74ufcOe9A0r16A0s3Rb5qyStXsfXTv9l05rzinYNLt+eKyn8v3XxjJe/tHhLcZrevP2H33t9TNVr9XuWLvXeCVxTKjMueXm3PKZV6vuSy6e+VmuS0or3jqzwmZz4eYZn5W6RMusAtUGU95izUcAwBMbMooNGdfKDGrzIltZXdjwxEBHn6z4Gwee+sqmWQGp2TR7fiBmb59SUqmpKStwsocvTyu/P23WHMX/e8dsmEjA7xqXaBXimcurMj0/y2IUUyxzVx5yXj5czDPaW+m1apXaz1u40XBHs1IQzjSvRtgKK3mS7G8DmTGzZMfewaGWi5dQml4hE5FsxB8IOTpdEtW6Z8sSlrEziKKOvs6KzmjpliKTQrSEdhDH0jF6xk8LEEvTNHwZfl0TCYwO1ffozYf0qrk9LITYWMBHC9RCb0t7RKK3ZhqIWd/SEZqd8cMxxFIMHWOW8BP0uOJng8kNBbu/hV88fq6xwmmwmLQS2jk0NEWrc9cf2FioW05wgaGww1ZdFzCuy0laiuIxnlCiMWok1zOqpFSrVvNWIuJZbVggVbqd95fnJ6rm9iqY2GTLsTeahSXGcDdvbVr21pmbZxiPlGjS1BLR9biGJ9YrNbR8CTuyN22WxAEAQBzLcdNpcYQQQtNZw6W3x1KxoN/PAOBihVxEEktJtiMqFJgY9yrNCTLB9AEO2jnionFCZ9R/4UWPEMchDJ/3cEIs1Hvmv358zJMg4Rfv3rd1Q5l5hhePKCrgsHllJoNccuXwAuUZnwpFefpU3WLD27jiVx+O9g21tdVeuOzi3IItL369yCiKh083gBBDhYJRDgNMKBELeCuT+puL+NCvPp6u7jGn03zPOg30nuseCVB3ukNfQDCMJ5AqFXKFQraacoe44m8HsmRrftnmdCnLuCfSdHJBPHa6k8RHf/XhyxV8QL66ydHR5AKzVhgf8ztJfI2/PXCuCa+/T1CeqhMvfycxzjKIK/724J20TfX2J6Uapfw7faTrLieu+NWF8k463cFocGzMNdyWlJusWt2wLM7nEvcpVxXKUXv0RIc3JldDTLHuUGmycDlZ/TgrQHyNX1U4BIj2DPU6MGXanu/tMIvjer/TxHeg4txd/D/mGRkq8nwcmwAAAABJRU5ErkJggg=="
    },
    "image6.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPwAAABDCAIAAAA3Vf+QAAAABmJLR0QA/wD/AP+gvaeTAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAgAElEQVR4nO2dd3wU57X3n2nbe9MW1dWq9wqSEBK9CRNw7Ni4xE5s45o4ie0U56a8yc39+Ca5uSnXOE4j7tjYuIANNqYJU9VR79Luqm7vO+15/5DACFQRzaDvf6DZmfPs/uaZ85xznjMIhBAssMCtBHq9DVhggWvNgugXuOVYEP0CtxwLol/glmNB9AvcciyIfoFbjgXRL3DLsSD6rzSQvSjLAiFkr48pV4OLh3eFRrcg+q8obMg+NGTzBpiJ/82Q/tHBER9JXx+rrhgw7Bgasrv8E4c3PrrwPEe3IPpzQJahKIqiWZamSIoiSYplWYamKTJMUjR9g82f7qYDe042dDlYDAAAAOVx2ay9ThoCknQ0fH6ooWs09FXOtLs6Dnx2vL5rGI4Pz++y9fe7KTZMOs9+fqihc36jw6+MkV95aKe5vvLdoxYSU+UYw6NBCWNtAvGpEpJDhLvafYqI2JxNq1OF19tMAAAAkByuf+eIS5OXl6ITIgAAAAdPfbL38BHlg7+9I04SnZLe8sH+Ghwuyk6WXW9bLwNI+hr27nPKEnOTYs4Nr3HfxzsOqx777ddSY1IzWt77tBqHi3NSLnd0N43og9bKN1/6zSvHocGUlaAXYQh7sbsLUBSE3SPdTbXdDgagGI4T/GV3//Dhb66M4vt6LaODXRgG+g7sQh5+oiI3Lhw8+uwHBxctu+PRomXhdz9pPebqLE3N4l8l6xn72cq9Bw52c1IK8/MW58QrONhUh8Kgv+/4zmHF0qJEk4Q7dhiiy126Tp+AangIhgsjUwpMn/+ptkOgjik1XC2Lp7KO9Y+01DbUnapsw+PKN2xaZlIgczoBy/p7K3cOiEqyMxKk/HPDSyld+4gJjeLjOG5ILkj8/E91HQJ17NLIyxvdTSN6XByhksKew/vrBnS/+NnKHD3OMBNVj6AopEP+zMwsu93Wfbb2xOGPDuwAqRlFJVFZHKku1pg26Ov4QpG2Kbcg1SDoOzPMUcQkZ+dGGekWggiSOEFcvnVwsKmho9pturtUT1wqguFTu97es6szYstt+WlRBgUfm0YnMOy01p0KRm3UauQEAADYuxsbjp+0K6JSilZLCAAAQPHIzAxuZeeAyRo2mLiXb/VlgCCEUB1lTEcA+fnrr75jc23ZtiVJMvvPw3BooPbDgHadTqMjAACsu6ep8YuqQUVUTNEyOQ4AQHBDZgb3aPtAvCUcmXBZo7tpRE9IElc98IufmD1/frdj2BeRX5Y5rS9COwfaGu58+5XXzeZTdc6sIrVKCQ0B9z5L4rpsnQCEbK0Nw9mpq7LjhcBzojocGojMjcYpiiWIOa+CaEfr8ff++tejo6Hy/7irdJID3K2HD59ocCx54a4VyTNOi3TQY24KmIolSjkKAGuvbbYMme2DfV3H2pHMlLU6FAEAAGl8BnMs5DQ7oUk7t5n2MqAHT3+8r6aWWLzt7mwtxhFpYkSamPiE4LEdL1fvjerekJQ9e2nSIbe5y23KFyqlKADA3txmNrfbB0a6ao6C5Ix1kTwEjI2uMuDsd8AE3eWM7mZayPJVBbdve2q1qevNF55/eW93cLq1Di7Xp5Xd8fyz96XBYEdDHw0A6RzyjDbGmLQSFLDOvtY+g04aHcEDnvrqMNcWoVO5z54ZJOe2foIuc+OpY8dOnzpV09LeSwkIZLLfyOty0ZDVGCSz+AFZKuQeaOJKUB4fBwCwJKKM1Wt1WuEQK5MJz50AIaRqYY87YHWE52Tv5cF6h8ydza1DwQlV6ly5AWf4HreLnMOpIB10DAwoxIREwAEAQBKVx+p1BoNoEKilgnGXDyGkalGv5/JHdzOJHgBMlbzhgWe/nYYc/sfv/3Gw0TeTRDnJ61dl5sfhbgbAUbPVbSEXJxj4AIRtHTV4klQVJQfAb7cLHZ2M3do0ROFz/boYMsgAaUJOUX5OrASdYu8CiuEoirI0M9kfLz4hQwY8FhRQKAYAAKgqM9XAtfebe0cyizMk50+P4jjuCIa9YWqOBl8OuK5w04OP/eL+HO2FfgPD0AgKcGw6X+1SGNLvcuMAjj9QVckJBh7Z339yOGF1pvz8PY3Nb3Q3l+gBQCUZq7d956kNWN0r2196r8E+k5D4GaU5+bkmHEBUFpeQe29xjARAgAjUmRWl6UYtAYA8tTwlvlCrJOTpxXrO3J6miDK+oLi8rCgvTi3Br8h2HQIneCINzWIMAwAAKIEGuqp7PG5OfoHMUdftHl+9sxRFqQVcGY8z/0vOCCrWRppSkjS8K+BIoQRfLApCSDIQAIAQaKi7qdPtDxVkaJ0tXW6KAQAASJHzGt1N49OfByGilt7zvW0NzS+8/b9/Mxl/+vgS7XQuJcITjIUAdPmlt+WPu9y8+BU/iB8/gJdYVpFYNj+bKObSWNIFJiAAAMhOfk+Q3pGhUS9L8LkEjuMCqVigiC0g62HQTwI1BwBgt3QjYESsZfqqm7nF6UaAIgCSrkFfrFRoUF7VZSwbdNndXq8f8rg8uV7DnziDjmVPkUs8OiZoH3EEGTpEEkqlmIMwHocjjKKAI9NFyAhhRGysp57y+EkAuAAAr2UQYf1GHdlf3QqL4+MAwADpHvLFzGN0N5/oAQB8ZeGd33+mqfGHn7z4v4mJhsc2xM0j8HL1QSBEaBZDLn3qBkbaa744Wm8J8VRajq9/0IoX33ePMSpLsW/I43SxsRoUAFn0osS4UBPpDStLC9VjDhhj7+ji6zJUkfJJL8iE3TaHNxRmEHTKyRlCFuVK5DKZiDeFN0B7elpOnu1zDnZ0e0Ns+j3PrYvnXnA6BEVQmgEMe+ElIEu5uhrP1Hd62XBvixWPUKr1Jn7/qdM97V2KTS88uyVeIItJ0n0y6ne42TgNCoAkOj3Z6HCS3lFlwWo1lzM+Op4uTRWtmPm7nZSbUvQAIKrU27c9d7bzmb++8pcEY8zP1qbx8asexbg8GOfgSBBCVWqEYOIfKE/17r+9a8UzVn17a7LIX7/nj0ffOEos2ZK+OL9Etr1/wJKYqYnAgMi44rbo0vUshuOcMU+YIi2N1WxKdlRc7KQ3O+sbOLV7V2W72Ydyp/hWIGQZihdTvmnj6sL4ScNgtK358/oRsXHR5qVRL7/43p6jtfevNsZccDpCHp3KP+m09ZvDTCIXQwAAkPEPdx2rc8QtXhavkY0SP3nwXx/L1//uT+vKB19pqgqFKZoFQo4+e4Pkrf5Bi5nRxGCAG1e6KmpxOYugOIeLAgAoytJYzaRkTDW6WXCTih4AIMzY+NRT7Q3f/92b27fnmF64M1l0vS26GMgyoeHOwztfPU1iRfffVzAxwWg7vuM/P++PWfHghkyVAAOoIW3F2nuzE9I1EhGWW5H0SqWlqzlOnS5HUYzg8M///pDxDzcf6dAULUtKjZh8jkZFhuI7H8gKUyyYbiKACCGSSCZP/0AwUFOPKwzGdD1vsHHQ0+8Ul/AuemzElm/b0rz90OG/vqrddltRglqIUiHS0eHQpi6K0PK5gPHZEIU0Jj5Gb9I88P2ELaxAzUcBAFx98aa4qkprY1NcZIYcQzGcg52TKWQCI82HO9RF5UlpU4xuFty8ogcIEb363ofWVv7b5vNeiyDGnHF3nDn+2Vvbj1kVxXfcVhzHvfBH9PZXvv/mKJG/OTdXggEAAEdnKl4fg3IFBAqAKnXDGtsHtb3NSmVRkv7Cz4Xdo02n6iSFi/OSY4RTSRrjiBTqec0BCNDkrynjCQQ4cLSfDYUtmcVJqotEiIuSC4vSTrYcPPL+pzoBuigvQcGTxJVUGCUyDgDkUEPdcIQ8vigpAgBMJNN8aQ+Hn7p6i33/sd6WOmVhnuECiYY9tqaTtZL8RXnJccLLj8HcxKIHINx1ukebW16+boNRMPPRAADIMFTQzwpEXHRqb3cirqY91QOMKmdTlmqu5gm0xsxV9//YcPqNE9V/fkv//H1L1OeKD+jhlsM1ZNSK5Ky48QgFihNc/Px8jsrSClfJvByR+CIzcYHUWLg8MUIn5Vzdn5an0PAAACDQ3dofdnFz4w0XF06429575bNeImnrk+vSo/QaEQ5QDBcolGN/dfXWdvN5aSmJ2kkKLlB5QuEyoQfjiCcqG+dLjIXLEzQ6KXc+o7uJRT9w/F8f1gWil96zslg7y0oxR//xAy/tQjb/sKJQL5hpJgnY2huqD771px0OzdpvZ26au4EcqSZSqomMF7dW/uLNPW/Vb1iyUj3+JzboHmWMWlX8mLLGYCjK4/QKlVIOhgEg0BsmuZMxDl8VFT39daHPemLvp9V9g36EM7VPz9JcfcHyspKM6OkKXKjh9j7GxWalXlLkQ5tPv3W6jSj75o8XZV1aGRbsqzuFKaJis+O4AFA2i6W/i05cmiA6bw4/Qn/pdTEOXznT6GbBzSp6X98Hb+7v5qR8fUVRwuxLP+Sa6OTFi8JK/pTlXheAEUKZSsYlWWALodN/QMDjEASO8wSTBZZxqUEs1oYs9sAF51ZEpepRkkd+mWfwDbfUnenhZaxUzrt0EuPKtPpohB9C8ClSRxBCyOAKpZg/w60/2F7jC9uiyhMvMYrxOkc5Ar1Efj6uSDvMVUfePSkovXtp6uipT+toIjk+UQxAeGCgq6Hem5Y8z2HNmptS9CHXmV1vnfBq1mxdnqebwXelnA4fAEK5JDjYW9cywpdlfC3fNOMsDwAAXKkhOe+2dUv2f95GU1NE4UP2rs4+s7XtyMnTVU0jwg8/UqQrVcaMpAjxBTU8NMVCFuNemO7FNGmbN+d+1Nd4YL88Tc0nfT6SolmMo4mQE+h8E4oIX5VatiZ1nmcBAADg727oowc4iSbNJUYhGM5BAMJ8mWimPUNnP93xd9ojcXaL2KiSCEpsPn7kuAF4PLg+Z3Gs4FrF124+0Yf9HZ/u+LAlWHDPXUWJETNN2aGGMw0uiTI91jdw9ovqGpunr3fo+79ca1JQg+3dQ04/jWAXZlcghADBBMoYY6RSwEEACATDFA0nLakBAACWCvq8TntYnlm0IpKOgC6nG+OFmZlTs4Qk7bZ7XQdPW/0uD48OuVyIKi4jJztydmuTawXV09ZK0GSKKWY20UNcEbV489PAqVCglHb1kz/PHrF5Bxxut1KjS8hOV83m6XpluMlEz4SHaj7YdbJZs+F7y1NjZlIIa6/aubfWbSrfkhWk+HxpRjqxv6OPRQEAIOwY6O8228MYgU4QPQtQjoxWROoUgmkDfmMItOmLtemLp0/oQgghAJckioSGko2bZ7zC9YQZrD/rRoBxccIkSTAEQZBzYxsDl2gzVj+Qcf6I5IRrYuWl3FSip73dVZ/VnAUrnv320oSpFQ/pcDDgtvfXH37txRetuV9flRipkgE5amv6aEe9bsWjEUIOAhTp5RvSr43ZKAJYlqWYGzR7NgFIBR1DvUOIMs6g4XWdrrZhWMqKFOUkR2KAJlmKBpMkmq83N4/omWDXqZ2v/fV1R94P8nw9TU2T1XexlM9h7hsYGezvqjvy/vv7WrlF3926LE0OAGDdQ/3m/pakom2cUZufq8ZpMhQK0+zE4hEIIUAQnCMUCbgYCgDAMBRBERSbz7NZGGFQC5vN7W19PpVBNK9g3FWHcVoOv/jE/5Brnrn79qizJ4KJceUbV8VdbDKkAp7OTgsQCaOucvnPZXFDf8NzAXo7q4/ufffTJlfl0/v+Aiav3oKQZRlmfL93CIgVZaUFaSYJAAD4zf1uhzM9X0nWV7VnSviEueZEQ8dIECcuDHBAloEYV2ksWbYoXs5lKMbvCwQDwYDPT1JibOKxs0acvX5TqcP72YfvfC5cvzg9US3AZ5sluOagHIFab4yzBBo/frtbk3rbXeuXJ0/0bViG8g63VR1553igbMn6u8qTbjyJIXMueIUsQ0MER9HxGRBCBrIAoNhcfijIMjTDIiiGzelj08GE3E6b3RVmWIphphwUgqAIgiAIgmI4jqEimVomFeAIAOHeowf37N5PZmbEZK5Zk6nj0oFAiJwsU39upg8MNrX113/4+5ebR2TZ235YkRmdmDFZ6HxWxgc89oGe3v4RN5TH5GQYFTfsfM8yYb/LSyEITUOeUCIWTqy2hoxnoLGudYTCZYY4U1SEXHjjTfRzFv1ox/49/3iFXPmrrWVGMQEA8Jze8Ydqh67g/kfyZ52SZMLmw//45d+rjHc88tCmxZprt2yfDjYUcDkcJMERyDWS2UiOpQL+oM814gwzGE+ukQl5QuEc6+0vAgZ9XhIQItGs8gQ3KCzl9wYYgi+ZNClxQzDHCcVtaao5+KY1txQf92LD3Sfer2/FhfnbLjwMsnQwQHP5BDapswsBG/I57TZ3iGQQAIC/+9ihz46cHqTxKed9lg4DcVTG4oqKEsP8lDUVKE+g0M9lokYJgZgQiCWaK2YCwhdNUeD1FQIlhFLp9TZieuYm+rDNbB0YlJWlGxVjqbrgwNkmUiVJyom7INEPSVfzof9527rkzjXL0w2TRHAxImLRnT/7r1V8Q6wCBQAQUn1cRgEazU7t60CWBly5Ti+a/Ig9e/Zs3759TmNZ4OagoqLisccem9NH5iR6ymUdHGnFljwWG8Ef095I66lRNWrMT7ywnh/hSLXGvGxehJQ/uYYRlKeKzVLFnvs3R2lMKzamzcnwiSgUirS0+Zxgga8qOp1urh+Zk+gdg52jnQOJqxM0ojGvJWBpbpGIU40phnPBWNJn76hr8yFM+spCo2Smyo0rRnFxcXFx8TW62AJfceYier+1e3i0LSb7yUjhmM8CrZ3VuEaVbNK4bTY/y9PyAj0Npxq7PJ7+/XVm5un1ZQmzaWsBSHt3R1tnn3tm9yY2Lc0ovc6BDQiCttYOi40S6yUUxbI+V0gk43KFCmrU4sU4LFeXYlQL594f5+rCkAzKmRBRZUgGm7qR2s3MHATEjpg7Rsy25A06OY4AAKCt+dChOpVxa4HM19zYYhEUbooO0oCbuaLUtnf3Ub87REMwaaoesqRnxDzs5aq0EQoxASj3QM/ZM7NZyHJiUuKks0j/Tz+Q4HBn1dkeH+BJJQIOAtlJ92RDOuC0OX1hBsFwgsNVaGJSstJUPEiTjsaDR8/0Vp2yx6VrYjJSkM7GtlGzV12+TO2zeT1t3bzbHr+jIFJ+le5N6B/t6uj1YAJZRKReIeHNuA2S8Q1bBkZpcXycboK7Sbp6zT6uUhOpvE57yki/0zFqsY6GubLohATNPGObLO13DA04whKdQSXmTXszz/6Xge5h63BDFxZt7uwZ4vMh7Wiqbh0S8xLkrp4eFgaVBjVPC9K0MYG+2toWZ8ZalVI8xWzHUsOndv7ypZNxW596fHNxBCY0LqnYtqRiTmO8fCDr6zj6x+/96N1WNnvj5tUZMVw6fFGnEARBAB0YaK1p6R11eLzO0cFRsXHNT/+5+/ESbpjxOMmULFPP0SaXIO/rKzaYjP5n/u/kWaHs+W9sYWoOjh79eMDlpy5f9IxnyInKJQIu55Kvj6Wcg1V7d+2v7UFiU9IXrZCIxTOJnnG3N1TWdyCm1cnxAADABDz9Dae9hvQENeHqaeztkodKikyzitFeaYLuoe6GIwdPtY9SSSu23LGmUMOdx+ORdLXte/k3uy3Lnv7J/aUm8XSHzn6wnoEOm6cDyUzoPn6w0ithfKgm5RuP33/a6vmiLbCiOLfAMHYc7bePdNoyk9QRkqlK7yBgWTpM0jQ9Rd+LqwqCq3I3fe/hE00v7IaahLXf/s4SAwcyk7TihizD0oHhjqYTn+z820cnRqsOnrYXlykFhrzV3LYPmhQZFVmFCQSwdXUIRWBZebECBDtcQ828uEVi/uXFqJmgs6/+5Du7Owse2lKSYLh47mN93ZXv/uG12qU/fHbrkkQJhmEzlRlDT/NnVZ02Yfq9uec6MQVGzn7yprnoQeXKkpyi2PZdNUcO8/QVBbOqpp4vLOX32JwBrlwpFXIxiS5p0XpTfkn1v/7wrzd+Rer//XS+6vIf4hAwDB0OMwzDIlN4GOeYtegZa2enfyhy63f+49EiGY4jACI4l4tlZZEUxeI8Hmdc4YzfYe+tk6aWq+RTblfCOZHLH3t58UMYTyC4HlMMIlAXb33m+e6u5w+88Y9P8hIfWXXJXrfz8GNzlkanFZSU7H73yNHKekvJ8iiOVBkcaPSok5QREQBQ3R1+gonMTRQAb79lqNkcv0ROewOkmEdwJmnWOgWQocOe4fYv9r366j9f85T+kSEmuW0CPrO5+QQv7u4YvWJW7WTh4PHDtrDfUHbPWKgXUqEQT1Py5H8RIqkQR1BJWrH2i32WfQcH8isir37lAxuyfvHWr148mfvdZ+9dliZFEBTDUUwZH6/gfNFa2TX4ZL7q8nu18BTZ3/jJq5tYjkA4RdDwPLO+vwe6mtw2c05mskEiFgr4AoGAz8FQjMPjC8VC7pdFJ16vta9qyKBWiEVTXxrBOAKpTCriXbflHqJK2fLgE1/XeT96+ff/t69l+n6LKIcfvXTdypK10tbGUYZlwh5Lx9lkgyBGxQewv2OE6ydyTFIQGrY6+quy4qS2uoZ+m42ci4oCwz21xw4224FUJSMxgpm0RJ9lGcjQBBdDZvd8hKNNjRRkIpOiMAAA9Dm6K3e+9vrf//Rx+3AIYAAAgEUnRHoYpLLJOgdbLx9UqDcVrlufb5zY7gRFURxSs2prODUISvBEMplEwJmxAGq2ovP0dw17HIq0yMmqSAEAIDjQ2lRd09xjHRjsMZdkRmlEN2wWehxBxsannnyoNFTz1kvb32/zznA0Ik/MLasojeUCQPpGLVZ1sjYqQooA14BVImbjM6MRgHMEfMgNdJ5p4UYpJQreDGecAE+hTy5csXx52aL0aAGBQnayN5+M1QxBdralI/6B9hAvLIgzIAAA/8BQX92ALF4SrjvT2DXqHj9lRJQUKuh+c2DaM10ZUJ4yeck9927Ki1JeOKNDCOdauzU/ZuldhAY7h1kbtzh9qkQ96+k68dlbH9fI8k2C2G8+sDhZeXWKBa4kKC927SPPtJ59Yvvbv3spLf5n2/Imbwg2Dlcuj5OJGQQBUv3SR3+O6iLVKACClC13xTA8NQEA0CYsuuvXhiBHpI3XiC5dhk4HxhPKeUJAuyT8K+fwuUc6GFLEkwgAABATKbWmJI6nZicetVF9vlKAL5KGIMcx7ALgGuzKQnGe6PqX0s3SAky9+M4HoylptmwKKSPi+EVLN8viMJ1GHpuXprrRp/lxuOol33rm8dauX77/2/9OSvzjw8sma0hxAQiOAQB44qj0c+lfrsp0fns+R6CMy5rqUTgrSIqeZi8hgiAIMtVETw63nzxZZYZynYzP0nhkek4SxfgghaAYAgBAuFK5JlrQ+fqxkbS7jBohF0AWIChAUZxlUYq6qp2BGI+tp/nM2WEA/Z7YpavTI+UX6gNCFkIWnXXXlXkzS9ETiqQcRdI0ByACfWquPjX3ihh1LcHV+fc88d2W3ude+dt/JyfH/7Q8+sbte4kikPYyHIxzcctwONp05uiho3ZtQoxGxne3vPva62jFc98r1yRw+GQ4SALAAQggPdbe2sNE+SMRwcZ2C2HUaGUcEA55uFgYl09RIxa01J45XdNsY6dLoZBApEvMWFKSqZpUTv6hnvaqao9My/G0nHztAK77cUVp1AW7wDmEgIU8h/+avRHxBssbXhdkeZueeuzRxaEzL77wu92Nw+Eb7EWC48CAuaaqpoMqL802KSZ4IoGew3vf237Aoy5Zu2nN0qJFWUk6lUrIAYgsKg0Hav+Ac+w4hgyFvQ6BeKS9wxX0MWPhTveIixNkIqOn6JMytu2Gphl6ShiGZmhm8gwfACBobm6p6/LF5S8pKzRpuR0dA0P+iXEDkSm/MKlI2vTp520Wz7VQ/vV3sG4AEHHSbQ9/v6XtRzve/6jqnlXJEfNJklwFmIBjtPPEx+9/9HGrcOUzdyxLFF8QwafdVbt3fXLWmv/j29NEAADIKhM3PPprSaRBK+YkGJh+f3+zC0TIAOBKY9KXfcs/KBAp8lIjdRIcAODrshJsMCXVMMWIBVF55VF55fMwnvZz1LqYmEIFdDX0dLci6Zs1FxUiEoaCr621O7f/+eV/coK3byzNiJXz5/z6i7mwIPoxCHF0VsGKtTxT4lVTPEv67WavIEYjnOsvyoZco/29Qywf10Zj/qCfZL/M1rJDVQdqLVbu8ucSx6oJEFyoTs4Yb5WWUJR07FBLW23fkmUxBMpTJxbfm3jBicnhM10enjhlecLVe1moODkrHQAAYMBuNTfZc4pjY6UXZd3CXhsZ9uvS9AAnXTZPOFJ2BVfzk7AgegAACNvrDh5oH1FseO6+otn1HIIgbD1z0i6IjEqKV8zwJUKaDLhHu08eOl51hHv7b7emyeYY2SIUxoyKJzJWdFbu+PPTP9sh/Mt37sw4V+VAWzs6QACm5xsn6JalaIiiGGYsLWgJ13cdq09V5ESIJ6zS6YDt7PEOnkqXsdo45TqG9ttto3ZXGCKXvl3h3PBYBhACqTxCo5iqlT0AAITcFkvrGVHy11SSi4K5dFflGztf3qt4bNdzFYZrEQFZED2Awa6Tuw7WDClWPLE6aZqM2gQQ4G7bv7NJtmxVdLxi2kIPANiA21K7//V/vnbMDO//GjtdkALHcQxFUAzDJ/lh+Nr4eFN2x5Hebqc7Qz4eJUJwgiOViaSSL42AtG+wo5dUGCI0cr4wY3lB4HhjT31PyuqJL1wMWGsGRfGmhCWp09gftNQc3XvgCwvDmXKzOkuHgDQ+v+z2LeWRU0uWdQ6bhxtg2gMxiov7DTsH20acrar8KO01ivnd8qJn3K173z9ugXF3bCmbeZphGRbFUMiSYUqQ+/DP83gi4cyOASZSGEu2fGPYBXbtQcCkaScAWJamw5TH4/H5QwGez+MJBIUEQeATu00iGAdhL2ygBPCYrCK9uc5u7g9kGjAAWTbsNJ8+UoOmLXGsjBQAAAQLSURBVDZERwAAEL4uf6kqkwYXb0QUxZaujMFneD2u0Lhkw0P5K+lps2EQoASXJ5j2RK6BLmt3e/qyKN0lW8XHlsA4Oss88/y5xUVPjRx748PmEK9065asmbyUkM1msZgFiSkSR8v+w409Pc6sinXFOVII4dQp0vHOCwRfplDIxFM//hn3cGvNwZPNlrNHGqhe7ue7lVRTYmZxQVZi5Jd3FYQQsmPtHL68gDLr9nUuzsHjb75KZ+kJj8MLZfrkvDJTtEY0fjUEJzj4pYpECf7MSWOU4AsJ/vw9/rDdOmixKtMjdZfeG2PtKab5Eq80t7ToqdbdLx8cCSZueKo0bqoy6PO4u1qrDnYSFTpvX10zXydiDx1qajUmZyYEmk8cr21xwIlNbyCAkIbalKK8nCQ1DwCaoujJSjnHQYXy6IxSYWy4pGzlVhIIRFIhny9VKGYuMkcIdWbxZm28LUiI+AhN0oAnVmsUV+JVf1cO0tZrsdYhJT+IVt0Aht3Conce/9ebrT5V6T3rcrQz9SBg+j574939lWDlr1USsT8uSxRseA/TZ8n0ShQguth0TBKCKHKR6AELhErN7NLuCIcn0UTP2FkBQgiRS9aUmECui5u2hOJ6M2rpsLYMGzfFqwWXprzHml5ewyrzW1X0oa6D/z7j1Cz71oOliVPWnIQDdtuozdxy6tAnb+w66Esq+0lOtJiPi+Pjmnf+p0WzaEOUUYAwQKWPV+mvhdEYysEI3Otn2BsrjzA5Qeuht95p58et3bKJ21Df2hVec++iGOEkjj8kw2wgJCSuWbXWrSh6GOqv+vdvfvT/DrNZuW2tbxLhSZdpTNjtcLpcTudQT2OrNQjEBVs2LtLgAEDK1XPyTLBgaQzPNmLtG2YhsHR0udmJ4Q0IIGCAPCY10RQl4wCAcwgCx1CCw7n8EAVXakpdvP7Q7v37Po3YsGZxrPSG1j7tbj74yb6A2E6xcvNw7IqHNpYlSi4q+4WUs+3Ehyc6XRG3b87UX6sNu7ei6AEEUGAsuwexe8NhmzM4xVEILpRGiOW6uKTsci4vMr5wY44SAQAAKuh1+qJkNmsfUOj0kSosRJEkybKTiJ6mWQiZgMdp661rbG7p7nXU1zfwEo2RSiEx93d8YoKo/HXffTCwt9fd1VgrAKnxerX4hq1m5emX3veEwe4M4Cg3rzx/aWnMRCcSBhzWvt625o5QZFHFutWbkqYqZrzizL2X5QK0Z6T280N9wYAwa1lBQuyMFaW0xzbY31R9qr65rUNYsDEvISE1JVLOnf22qkvwjXR1d9sInSk2WjnTNqEbFugeaO+xOAhNcmKs/JpW+S2IfoFbjhvaK1xggavBgugXuOVYEP0CtxwLol/glmNB9Avccvx/ywQ/bs4Kek8AAAAASUVORK5CYII="
    }
   },
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 具体算法描述\n",
    "\n",
    "1.随机选取 k 个聚类质心点\n",
    "\n",
    "2.重复下面过程直到收敛\n",
    "\n",
    "- 对于每一个样例 i，计算其应该属于的类：\n",
    "\n",
    "![image5.png](attachment:image5.png)\n",
    "\n",
    "- 对于每一个类 j，重新计算该类的质心：\n",
    "\n",
    "![image6.png](attachment:image6.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Numpy 实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy import *\n",
    "import time\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# 计算欧氏距离\n",
    "def euclDistance(vector1, vector2):\n",
    "    return sqrt(sum(power(vector2 - vector1, 2)))\n",
    "\n",
    "# 用随机样本初始化质心\n",
    "def initCentroids(dataSet, k):\n",
    "    numSamples, dim = dataSet.shape\n",
    "    centroids = zeros((k, dim))\n",
    "    for i in range(k):\n",
    "        index = int(random.uniform(0, numSamples))\n",
    "        centroids[i, :] = dataSet[index, :]\n",
    "    return centroids\n",
    "\n",
    "# k-means\n",
    "def kmeans(dataSet, k):\n",
    "    numSamples = dataSet.shape[0]\n",
    "    # 第一列存储示例所属的集群\n",
    "    # 第二类存储此样本与质心间的权重\n",
    "    clusterAssment = mat(zeros((numSamples, 2)))\n",
    "    clusterChanged = True\n",
    "    \n",
    "    # 第一步：初始化质心\n",
    "    centroids = initCentroids(dataSet, k)\n",
    "    \n",
    "    while clusterChanged:\n",
    "        clusterChanged = False\n",
    "        # 遍历所有示例\n",
    "        for i in range(numSamples):\n",
    "            minDist = 100000.0\n",
    "            minIndex = 0\n",
    "            # 遍历所有质心\n",
    "            # 第二步：找到最近的质心\n",
    "            for j in range(k):\n",
    "                distance = euclDistance(centroids[j, :], dataSet[i, :])\n",
    "                if distance < minDist:\n",
    "                    minDist = distance\n",
    "                    minIndex = j\n",
    "            \n",
    "            # 第三步：更新集群\n",
    "            if clusterAssment[i, 0] != minIndex:\n",
    "                clusterChanged = True\n",
    "                clusterAssment[i, :] = minIndex, minDist ** 2\n",
    "        \n",
    "        # 第四步：更新质心\n",
    "        for j in range(k):\n",
    "            pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]]\n",
    "            centroids[j, :] = mean(pointsInCluster, axis = 0)\n",
    "            \n",
    "    print(\"集群完成\")\n",
    "    return centroids, clusterAssment\n",
    "\n",
    "# 仅可用于二维数据的集群的显示\n",
    "def showCluster(dataSet, k, centroids, clusterAssment):\n",
    "    numSamples, dim = dataSet.shape\n",
    "    if dim != 2:\n",
    "        print(\"错误，仅可用于二维数据\")\n",
    "        return 1\n",
    "    \n",
    "    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']\n",
    "    if k > len(mark):\n",
    "        print(\"错误，k 值过大\")\n",
    "        return 1\n",
    "    \n",
    "    # 绘制所有示例\n",
    "    for i in range(numSamples):\n",
    "        markIndex = int(clusterAssment[i, 0])\n",
    "        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])\n",
    "        \n",
    "    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']\n",
    "    # 绘制质心\n",
    "    for i in range(k):\n",
    "        plt.plot(centroids[i , 0], centroids[i, 1], mark[i], markersize = 12)\n",
    "    \n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 测试"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "第一步：加载数据\n",
      "第二步：聚类\n",
      "集群完成\n",
      "第三步：显示结果\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXYAAAD8CAYAAABjAo9vAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAGKRJREFUeJzt3X+IJGl9x/HPt+d2iIUGYW9R9G6qJSTgYQzhBhH8I1k1cuqi5D9N33FshIZVQcmJ6PXf85dgDCjKkLgEu8FIVJIsieZkJ+SfJDirp0RP5ZDu9dToaiAejHjczjd/1PTtbE/3THV3/XjqqfcLitmp6a5+qnv59FNPPT/M3QUAiEen7gIAAIpFsANAZAh2AIgMwQ4AkSHYASAyBDsARIZgB4DIEOwAEBmCHQAic08dL3rvvfd6t9ut46UBoLFu3LjxC3e/cNbjagn2brer/f39Ol4aABrLzCZ5HkdTDABEhmAHgMgQ7AAQGYIdACJDsANAZAh2AJKk0UjqdqVOJ/s5GtVdIqyKYAeg0Ujq96XJRHLPfvb7cYX7aDRSt9tVp9NRt9vVKKaTm0GwA9BgIB0c3L3v4CDbH4PRaKR+v6/JZCJ312QyUb/fjzbcrY41T7e3t50BSkA4Op2spj7LTDo8rL48Ret2u5pMTo7tSdNU4/G4+gKtyMxuuPv2WY+jxg5AW1vL7W+amzdvLrW/6Qh2ANrZkZLk7n1Jku2PwdaCb6hF+5uOYAegXk/a3ZXSNGt+SdPs916v7pIVY2dnR8nMN1eSJNqJ5ZtrRi2TgAEIT68XT5DP6h2d2GAw0M2bN7W1taWdnZ0X9seGm6cA0BDcPAWAliLYASAyBDsARIZgB4DIEOwAEBmCHQAiQ7ADQGQIdgCIDMEOAJEh2AEgMgQ70CIsf9cOBDtKQ4iEpQ3L3yFDsKMUhEh4Yl/+DncQ7CgFIRKeRYsFRbqIUKsR7CgFIRKe2Je/wx0EO0pBiIQn9uXvcEdhwW5mG2b2TTO7VtQx0VyESHhiX/4OdxRZY/+ApKcKPB4ajBAJU68njcfS4WH2s6mfx2g0UrfbVafTUbfb1Yi78ncpZM1TM7tP0tsl7Uj6iyKOieaLeQ1N1Gc0Gqnf7+vg6O78ZDJRv9+XpGjXMF1WUTX2T0j6sKTDRQ8ws76Z7ZvZ/q1btwp6WQCryjvOILTxCIPB4IVQnzo4ONCALlcvWDvYzeySpJ+7+43THufuu+6+7e7bFy5cWPdlAawh7ziDEMcj3FzQtWrR/jYqosb+BknvMLOxpM9LeqOZDQs4LoCS5B1nEOJ4hK0FXasW7W+jtYPd3T/q7ve5e1fSuyRdd/eH1y4ZgNLkHWcQ4niEnZ0dJTNdrpIk0Q5drl5AP3aghfKOMwhxPEKv19Pu7q7SNJWZKU1T7e7ucuP0mEKD3d3/zd0vFXlMAMXLO84g1PEIvV5P4/FYh4eHGo/HhPoMauyoRGg9K9ou7zgDxiM0k7l75S+6vb3t+/v7lb8u6jHtWXH8JlySEBDAsszshrtvn/U4auwoXYg9K4CYEeyBibHJIsSeFUDMCPaAhDgYpAgh9qzAepirJWytC/aQa8SxNllU1bMi5M82JtO5WiaTidz9hblaCPeAuHvl24MPPuh1GA7dk8Q9qw9nW5Jk+0NgdnfZjm9pmv09TcMp7zKGQ/eXvSw7l5e9rPhzCP2zjUmapi7pxJamad1Fi56kfc+Rsa2qsYdeI17UNGHW/OaZV7xCevbZ7N/PPpv9XqTQP9uYMFdL+FoV7KHfxJvXZGGWBfpxBwfSww83p7lhb0+6dOlO8B4cZL/v7RX3GqF/tjFZNCdLp9OhOSYQrQr20G/izRsMctowgybU3mdDfarocA/9s43JvLlaJOn27du6fPky4R6CPO01RW+0seeXpovb3Y+3v1dhOFyurf/69ZPv9+yWJNnjiihb0z7bJhsOh25mc9vaz58/X3fxoqWcbeytCnb35cOpbvMCa3Yzq6ccpwVnnlAvI9yb9Nk23bxQn255DYdDT9PUzczTNPUhH9qpCPaITAOrzhr7otef99rLhHrR4Y7qrBvsw+HQkyS563lJkhDup8gb7K1qY2+q6QLEw2F9M+3lvTm5qE39LGXcUEW5zp8/v9T+WU1Y4q6xA7HypH/RGzX21a3a3LBuM8X58/Nr2rPNqXnuCYRwv6AJQm9aGg6Hvrm5eVeNe3NzM3eNe1EbvVXRtphDiFcUoimmXU4LgXnt4+fOZaGcNzTyBvsqzTA0x5zUlJvBV65c8Y2NDZfkGxsbfuXKldzPDX2gU4jlI9hb5KwQyFOLPis0Fo2KnVe5oo19fcvc06jLujXaEGvEx4V4RUGwt8hZIXDaVAV5Q2PZoLl+Pf/rEuonLfNFWpciarRF94op8njU2An2Wp0VAnnbvU8LjVWaBh5/nFBfVQg19rNCMrQabdFXACFeURDsLXJWCOTpC58nNFa5mff444u/eAj1xepuY88TaqHVaMsoT2j97An2FskTAsdD+fx5983Nk0F7/nw5wTGvzZ1QP1udvWLyhGRoNdrQriDKQLC3zLIhMBzO7+lSVq3weLgT6uHLG5Ih1WhDu4IoA8GOM5XVjrvoS+b69ex3Qj18TQzJ0K4gykCw40xl9Lyou20YxagyJIus9Yd0BVEGgh1nKqPGHkJvDhSjipBsQy27SHmD3bLHVmt7e9v39/crf13cbbp49vHpOpIkmxO+11vtmJ1OFuWzzKTDw9WOiXh1u11NJpMT+9M01Xg8rr5AgTOzG+6+fdbjmASsxeYt7LFOqEsseIHlsMxeOQj2lpvOHHl4mP1cJ9Sl+cv7VTUDJZpn0TJ7i/YjH4IdhZq9Cjh/XnrRi6RHHmnOGq2ozrxl9pIk0Q41gbUQ7Cjc9Crgc5+Tfv1r6Ze/zNrdy16jdTTKvjw6Hb5EmqLX62l3d1dpmsrMlKapdnd31Vv30rHluHmK0nS7WZjPStMs+ItUxo1gIDTcPEXt8q66VITB4OSqTQcH2X6gbQh2lKbKHjJVfokAoVs72M3sfjPbM7OnzOw7ZvaBIgqG5quyhwzdLIE7iqixPy/pMXd/taTXS3qfmT1QwHHRcGX0k1+EbpbhaOwC0BG5Z90DuPtPJf306N/PmtlTkl4p6bvrHhvN1+tVc/Ny+hqDQdb8srWVhTo3Tqs1Go3U7/d1cHTDYzKZqN/vSxI9XSpUaK8YM+tK+ndJr3H3X838rS+pL0lbW1sPzhtGDKDZmCKgXJX3ijGzF0v6oqQPzoa6JLn7rrtvu/v2hQsXinpZAAFhioAwFBLsZnZOWaiP3P1LRRwTJzEAB6FjioAwFNErxiT9jaSn3P3j6xcJ80wH4Ewm1YziBFbBFAFhKKLG/gZJj0h6o5k9ebS9rYDj4hgG4KAJmCIgDEwp0BDMcw6AKQUiwwAcNNm8vu30dy9RnmWWit5YGu+ORQs/z3sca4miieYtf3fu3Dnf3NxkSbwliaXxwrfsjISjEQNw0DyL+rbPQ3/30+VtiiHYa1TltLZAXTqdjvLmjJnpkJtGC9HG3gDMSIg2WKYPO/3di0Gw14gbomiDeX3bz507p83Nzbv20d+9OAR7jZiREG0wr2/71atX9dnPfpb+7iWhjb1m3BAFkFfeNva1p+3Feqqa1hZAe9AUAwBzNHkAFTV2AJjR9AVDqLEDwIzBYPBCqE8dHBxo0JBZ9wh2AJjR9AVDCHYAmNH0BUMIdgCY0fQFQwh2AJjR9AVDGKAEAA3BJGA4gcWwgXagH3tLzM79Pl0MW2LkKxAbauwtwWLYQHsQ7C3B3O9AexDsLcHc70B7EOwtwdzvQHsQ7C3R62WLZKepZJb9XLRoNoBmo1dMizD3O9AO1NgBIDIEOwBEhmAHgMgQ7AAQGYIdACJDsANAZAh2AIhMIcFuZg+Z2ffN7Gkz+0gRxwQArGbtYDezDUmfkvRWSQ9IereZPbDucQEAqymixv46SU+7+w/d/TlJn5f0zgKOCwBYQRHB/kpJPzr2+zNH+wAANSgi2G3OvhMLqZpZ38z2zWz/1q1bBbwsgBjs7e2p2+1qb2+v7qJEo4hgf0bS/cd+v0/ST2Yf5O677r7t7tsXLlwo4GUBNN3e3p4uXbqkyWSiS5cuEe4FKSLYvy7pd83sVWa2Keldkv6xgOMCiNg01A+O1mw8ODgg3AuydrC7+/OS3i/pq5KekvQFd//OuscFEK/ZUJ8i3ItRSD92d/9nd/89d/8dd2dNHgALLQr1KcJ9fYw8BVCZs0J9inBfD8EOoBJ5Q32KcF8dwQ7UZDQaqdvtqtPpqNvtajQa1V2k0iwb6lOE+2oIdqAGo9FI/X5fk8lE7q7JZKJ+vx9tuF++fHnpUJ86ODjQ5cuXCy5R3Ah2oAaDwWBuj5DBYFBTicp19epVJUmy0nOTJNHVq1cLLlHcCHagBjdv3lxqf9NdvHhR165dWzrckyTRtWvXdPHixZJKFieCHajB1tbWUvtjsGy4E+qrI9iBGuzs7JwIuCRJtLMT9zCQvOFOqK+HYAdq0Ov1tLu7qzRNZWZK01S7u7vq9Xp1F610Z4U7ob4+gh2oSa/X03g81uHhocbjcStCfWpRuDch1JvQTZVgB1CL2XBvSqg3oZsqwQ6gNtNwT9M0+FCXmtNN1dxPrIlRuu3tbd/f36/8dQFgHZ1OR/My08x0eHhY+uub2Q133z7rcdTYASCnpnRTJdgBIKemdFMl2AEgp6Z0UyXYAWAJq3ZTrbKb5D2lHRkAIOlON8lpj5ppN0lJpdT2qbEDQMmq7iZJsANAyaqezZNgB4CSVd1NkmAHgJJV3U2SYAeAklXdTZIpBQCgIZhSAABaimAHgMgQ7AAQGYIdACJDsIdkNJK6XanTyX4GtioLgGYg2EMxGkn9vjSZSO7Zz36fcAcCFur6pwR7KAYDaWYuCR0cZPsBBCfk9U/pxx6KTierqc8ykypYcgvAcrrdriaTyYn9aZpqPB6X8pr0Y2+aRXNGBLbkFtot1KaHOlQ9sdcy1gp2M/uYmX3PzL5tZl82s5cWVbDW2dmRZuaSUJJk+4EAhNz0UIeQ1z9dt8b+hKTXuPtrJf1A0kfXL1JL9XrS7q6UplnzS5pmv5e15BY9cLCkqucUD13Q65+6eyGbpD+VNMrz2AcffNBRo+HQPUncs1b9bEuSbD+wgJm5pBObmS18znA49DRN3cw8TVMfRvZ/rOrzk7TvOTK2sJunZvZPkv7O3YdnPZabpzXrdrPulLPSVCrppg+ab9mbhbPLwUlZjTbExZ+borCbp2b2NTP77znbO489ZiDpeUkLr+fNrG9m+2a2f+vWrbzngXUsam5ZdHMngJs+CNeyTQ803dQoT7X+tE3So5L+Q1KS9znBNcUMh+5p6m6W/YzhcvG05pY0vXv/dEvTukuNwC3T9LBK0w1Op5xNMeuG+kOSvivpwjLPCyrYY21vPi28Yz1nBCVN07nBnlKBWFneYF+3V8wnJb1E0hNm9qSZfWbN41WvjhGfq/ZIWeZ5pzW3VN0DB60UdK+R2OVJ/6K3oGrsZvNrtmVdLq5aW172eTS3IACx94qpmqruFbOMoHrFVN1DZNXXW/Z500nFjl+NJAk1c6DBmFIgr6pGfE6bUeaFs3R2j5Rle7LQ3AK01j11F6B206AbDLKQ3NrKQr3IAJxXe5511jDkra35XwqnPa/XI8iBFqLGLmXhNx5nsyiOx8WH4bwbtMfluUJgLhkAORHsVTitmSVvEwlNKwgIszwuFsR7k+cOa9FbUL1iqkAPFURkOBx6kiR39U1PkoQeL17+e6OK+rEjD5pREJGipgoIomZbsFCmUSDYq7BqM8reXtaTZm+vkmICeRSxwESsc7uHsvgG/dhDNBpJjz0m/exn2e+bm9JXviJdvFhvuQAVsyRcHcvKVaHs86Ife1ONRtJ73nMn1CXpueekhx6i5o4gFDFVQCg126KFMo0CwR6axx6TfvObk/ufe066dIlwR+16vZ52d3eVpqnMTGmaLj3HesjLyq2jiPemEHnusBa9VdorpklT8l6/Pr/3zOz8MNev111SYC30rFmN6BWjOyM+J5MsFieT7PcQb9Ds7WU18rMcHFBzR+MFU7ONVNzBXvWUvKtOxzsN9dNGpx5HuKNiZXRN7PV6Go/HOjw81Hg8JtSLlKdaX/RWWVNMlVPyrjod7/XrJ5+Xd6NZBhWg2SQcoilGiyfIKuMGzapXB5cv56+pzzo4yJ6/yOwVxHvfu9oVBVotlEE3yC/uYK9yxOeqC0RfvXqyjHklSfb8eebdX/j0p5txvwFBibVrYsziDvYqJ85a9erg4kXp2rXlwz1JsuctGrR01oySUvlLAKIxTmtDD7VrYoxTEhQmT3tN0VuUk4BduTK/HfxNb8rX3XKZtvY8beuL7i9UtQQgGuOsNvQQ29hDLFMVlLONnWAvyqIZHGcD9rQbqnnCPe8N00XlYYbJSjVhzc80Te8KyOmWHvu/sc55lPEe5ClzjAj2quWtIZ8VpqeF+zK9YOb10pl3vACDJhZNqVWa2dyQtAKu5sp6D8osc8jiC/bQR5DmrSHnaf6YF+6rdG2cfc+uXAn7PYxMU2qVZZYz77GXrdU35b0tWlzBvmof8SrNK+OiWnye/3zHw53+6o3UlFplmVcWed6DVV6/KVdDRYsr2JuyAtG8GvI6X0jXr2fHKSPUQ78CikCTapVl3QvI8x6s+j414f5F0eIK9ipHkBYtxABtwhVQBNpaqzwuz3vQlCubEMQV7E2psVehiC8K3s/KtLFWOeus96BJVzZ1iyvYqWFminofmnwFhOjMq9VPa/Ft/TJcJG+wN2PkaZUjSENW1GyVVc6hA5zh+BS+kmRmWa1TimYt1Kqx5mmTdDpZ3XqWmXR4mP8403lkjn9JJEk7vywRlFjXQi0Ka57GqKiaNldACBQTjhWDYG+SImer7PWk8Tir6Y/HhDqCsGhisU6nQ3PMEgj2JqGmjcjt7OwomTPT6e3bt2lrXwJt7ACCMhqN9Oijj+r27dsn/tb2tvZK29jN7ENm5mZ2bxHHC9Kq65kiXHymQer1ejpc0BlgUVs7c7PPyNMn8rRN0v2SvippIunePM9p3OyO9KOPD59p0BYNWtrY2DjRr71NI3xV1QAlSX8v6Q8kjaMNdkZqxifwz7TtI1bnhfWi0G7TyNVKgl3SOyT91dG/4w12RmrGJ+DPtE010NMMh0Pf2Ng4M7TbNNdM3mA/8+apmX1N0svn/Gkg6XFJb3H3/zOzsaRtd//FguP0JfUlaWtr68F5gxCC1e1miz/PStOsqyCaJ+DPlEE6d3Q6Hc3LKDN7oR2+Te9XYTdP3f3N7v6a2U3SDyW9StK3jkL9PknfMLN5XwJy911333b37QsXLix3NnUrsv84whDwZ8ognTvyLKQ9r4tkkiTaCeCzrE2ean2eTTE3xbiHOf1u1WJ7DwI9nza1GZ8lb7NUW+5JqOrZHaMP9rajF0llaGO/W1tCO4+8wc4AJeQTcJt0jEajkQaDgW7evKmtrS3t7Oyoxwjj1svbxk6wI5+iZpYEsDJmd0SxmMMdaAyCHfkE3IsEwN0IduTDzJJAY9xTdwHQIL0eQQ40ADV2AIgMwQ4AkSHYASAyBDsARIZgB4DI1DLy1MxuKVtxKVb3Spo7fXGk2nS+bTpXifMNTeruZ06PW0uwx87M9vMM+41Fm863Tecqcb5NRVMMAESGYAeAyBDs5dituwAVa9P5tulcJc63kWhjB4DIUGMHgMgQ7CUzsw+ZmZvZvXWXpUxm9jEz+56ZfdvMvmxmL627TEUzs4fM7Ptm9rSZfaTu8pTJzO43sz0ze8rMvmNmH6i7TGUzsw0z+6aZXau7LOsi2EtkZvdL+hNJbVhe/glJr3H310r6gaSP1lyeQpnZhqRPSXqrpAckvdvMHqi3VKV6XtJj7v5qSa+X9L7Iz1eSPiDpqboLUQSCvVx/KenDyhYkjpq7/6u7P3/0639Kuq/O8pTgdZKedvcfuvtzkj4v6Z01l6k07v5Td//G0b+fVRZ4r6y3VOUxs/skvV3SX9ddliIQ7CUxs3dI+rG7f6vustTgzyX9S92FKNgrJf3o2O/PKOKgO87MupL+UNJ/1VuSUn1CWSUsigV8WWhjDWb2NUkvn/OngaTHJb2l2hKV67Tzdfd/OHrMQNll/KjKslXA5uyL/krMzF4s6YuSPujuv6q7PGUws0uSfu7uN8zsj+suTxEI9jW4+5vn7Tez35f0KknfMjMpa5b4hpm9zt3/p8IiFmrR+U6Z2aOSLkl6k8fXj/YZSfcf+/0+ST+pqSyVMLNzykJ95O5fqrs8JXqDpHeY2dsk/Zak3zazobs/XHO5VkY/9gqY2VjStruHPLnQWszsIUkfl/RH7n6r7vIUzczuUXZT+E2Sfizp65L+zN2/U2vBSmJZjeRvJf2vu3+w7vJU5ajG/iF3v1R3WdZBGzuK8klJL5H0hJk9aWafqbtARTq6Mfx+SV9VdiPxC7GG+pE3SHpE0huPPs8nj2q0aABq7AAQGWrsABAZgh0AIkOwA0BkCHYAiAzBDgCRIdgBIDIEOwBEhmAHgMj8Py9uN0P8jV0lAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "seterr(divide = 'ignore', invalid = 'ignore')\n",
    "\n",
    "print(\"第一步：加载数据\")\n",
    "dataSet = []\n",
    "fileIn = open('F:/NumPy-Learn/NumPy 进阶篇/Data/testSet.txt')\n",
    "for line in fileIn.readlines():\n",
    "    lineArr = line.strip().split('\\t')\n",
    "    dataSet.append([float(lineArr[0]), float(lineArr[1])])\n",
    "\n",
    "print(\"第二步：聚类\")\n",
    "dataSet = mat(dataSet)\n",
    "k = 4\n",
    "centroids, clusterAssment = kmeans(dataSet, k)\n",
    "\n",
    "print(\"第三步：显示结果\")\n",
    "showCluster(dataSet, k, centroids, clusterAssment)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法分析\n",
    "\n",
    "k-means 算法比较简单，但也有几个比较大的缺点：\n",
    "\n",
    "- （1）k 值的选择是用户指定的，不同的 k 得到的结果会有挺大的不同。\n",
    "\n",
    "\n",
    "- （2）对 k 初始质心的选择比较敏感，容易陷入局部最小值。\n",
    "\n",
    "\n",
    "- （3）存在局限性，如对非球状的数据分布不能处理。\n",
    "\n",
    "\n",
    "- （4）数据库比较大的时候，收敛会比较慢。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
